//============================================================================
// Name        : Prisons_map.h
// Author      : Andrey Bicalho Santos e Clayson Sandro Celes
// Version     :
// Copyright   : Your copyright notice
// Description : Genetic Algorithm in C++, Ansi-style
//============================================================================

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <stack>
#include "CImg.h"
#include "Individual.h"

#define PENALTY 1
#define BONUS 1

#define TAM_MAX_LINHA 1024

using namespace std;
using namespace cimg_library;

void pera(){
	cout << "\nOi!\n";
	string x;
	cin >> x;
}

typedef struct{
	int x,y;
}Point;

string *load_map(FILE *fl, int *num_linhas_mapa);
int count_lines(FILE *fl);
int **get_reduced_map(int **mapa,Point dim_map,Point *dim_reduced_map);
string *build_final_map(int **labirinto,Point dim_labirinto,int **solution_map,Point dim_solution_map);
int **preProcessing(int **mapa,Point dim_map);
int **copy_map(int **map,Point dim_map);
void clone(int **origem,int **destino,Point dim_map);
int **str_map2bin_map(string map[], int num_linhas,Point *dim_labirinto);
void printMapa(int **map,Point dim_map);

int get_number_of_valid_space(int **map, Point dim_map);
Point FindStartPoint(int **map,Point dim_map);
Point FindEndPoint(int **map,Point dim_map);
int count_in_genes(int **solution_map,int **map,Point dim_map);
int count_out_genes(int **solution_map,int **map,Point dim_map);
int *get_out_gene(int **solution_map,int **map,Point dim_map);

double euclidian_distance_2D(Point ponto1,Point ponto2);
double walk(Individual *ind,int k,int n_ind,int **map,Point current_point,Point dim_map,float fit);
CImg<int> update_display(int **map,CImg<int> cimg_labirinto);
int **InsertSolution(Individual *ind,int k,int **map,Point dim);
int count_marker_genes(Individual *ind,int k);
bool is_valid_option(int **labirinto,Point dim_map,Individual *ind,int k,int index);
bool is_connected(Individual *ind,int k,int **map,int **original,Point dim_map,int index1,int index2);
bool is_end_start(Individual *ind,int k,Point dim_map,Point start,Point end);
bool is_end_start_connected(Individual *ind,int k,int **map,int **labirinto,Point dim_map,Point start,Point end);
bool is_some_valid_4_connected(int gene_index,int **map,int **labirinto,Point dim_map);
bool is_gene_end(int gene_index,int **labirinto,Point dim_map);
bool is_gene_start(int gene_index,int **labirinto,Point dim_map);

bool is_wall(int **map,int x, int y);
bool is_start(int **map,int x, int y);
bool is_end(int **map,int x, int y);
bool is_in(Point current_point, Point dim_map);
bool is_inside(int x,int y,Point dim_map);
bool check_north(Point cp,int **map,Point dim);
bool check_south(Point cp,int **map,Point dim);
bool check_east(Point cp,int **map,Point dim);
bool check_west(Point cp,int **map,Point dim);

//---------------------------------------------------------------------------------------------------------------------------
double fitness_MazeProblem(Individual *ind,int k,int n_ind,int **map,int **labirinto,Point start,Point end,Point dim_map,int free_space){
	stack<Point> mystack;

	double fit = 0.00000;
	int num_de_uns = 0,num_de_zeros = 0, num_genes = ind[k].getNumGenes();

	for(int i=0;i<num_genes;i++)
		if(ind[k].getGene(i) == 1)
			num_de_uns++;
		else
			num_de_zeros++;


	for(int i=0;i<num_genes;i++){
			if(is_valid_option(labirinto,dim_map,ind,k,i)){
				fit = fit + 1/(double)num_de_uns;
				if(is_some_valid_4_connected(i,map,labirinto,dim_map)){
					fit = fit + 1/(double)num_de_uns;
					//int i1 = i/dim_map.y,j1 = i % dim_map.y;
					//cout << "\nPossui algum 4-connected:    Gene: " << i << " = " << ind[k].getGene(i) << "   map: (" << i1 << "," << j1 << ") = " << map[i1][j1] << "    labirinto: (" << i1 << "," << j1 << ") = " << labirinto[i1][j1] << "\n";
					//pera();
				}

			}
			else{
				fit = fit - PENALTY ;

			}

	}


	if(is_end_start(ind,k,dim_map,start,end)){
		fit = fit + BONUS;

	}
	else{
		fit = fit - PENALTY ;
	}

	return fit;
}
//-----------------------------------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------------------------------
//sugestao: inicializar os individuos com todas as solucoes possiveis (caminhos validos == azul)
//e maximizar o numero de 0's (branco) dentro do labirinto!!
//so chamar a funcao int get_number_of_valid_space(int **map, Point dim_map); para pegar o numero de 0's no mapa
//introduzir esse valor na formula... no numerador
/*double fitness_MazeProblem(Individual *ind,int k,int n_ind,int **map,int **labirinto,Point start,Point end,Point dim_map,int free_space){
	double fit = 0.00000;

	int num_de_uns = 0, n_valid_place = get_number_of_valid_space(map,dim_map);
	//cout << "\n" << n_valid_place << "\n"; pera();
	for(int i=0;i<ind[k].getNumGenes();i++)
		if(ind[k].getGene(i) == 1)
			num_de_uns++;

	for(int i=0;i<ind[k].getNumGenes();i++){

		if(i <= ind[k].getNumGenes()/2){ //verifica vertical
			if(is_connected(ind,k,map,labirinto,dim_map,i,i+dim_map.y)){
				fit = fit + (n_valid_place/(double)num_de_uns);
			}
			else if(is_valid_option(labirinto,dim_map,ind,k,i) && !is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
				fit = fit - (1/(double)num_de_uns);
			}
			else if(is_valid_option(labirinto,dim_map,ind,k,i)){
				fit = fit + (1/(double)num_de_uns);
			}
			else if(!is_valid_option(labirinto,dim_map,ind,k,i)){
				fit = fit - PENALTY;
				//fit = fit - num_de_uns;
			}
			else{
				cout << "\nOpcao invalida 1!\n"; pera();
			}
		}
		else{
			if(is_connected(ind,k,map,labirinto,dim_map,i,i-dim_map.y)){
				fit = fit + (n_valid_place/(double)num_de_uns);
			}
			else if(is_valid_option(labirinto,dim_map,ind,k,i) && !is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
				fit = fit - (1/(double)num_de_uns);
			}
			else if(is_valid_option(labirinto,dim_map,ind,k,i)){
				fit = fit + (1/(double)num_de_uns);
			}
			else if(!is_valid_option(labirinto,dim_map,ind,k,i)){
				fit = fit - PENALTY ;
				//fit = fit - num_de_uns;
			}
			else{
				cout << "\nOpcao invalida 2!\n"; pera();
			}

		}


		if(i % dim_map.y == 0){ //verifica horizontal
			for(int n=i;n<dim_map.y;n++){
				if(n == i){//inicio
					if(is_connected(ind,k,map,labirinto,dim_map,i,i+1)){
						fit = fit + (n_valid_place/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i) && !is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
						fit = fit - (1/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit + (1/(double)num_de_uns);
					}
					else if(!is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit - PENALTY;
						//fit = fit - num_de_uns;
					}
					else{
						cout << "\nOpcao invalida 3!\n"; pera();
					}
				}
				else if(n == dim_map.y-1){//final
					if(is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
						fit = fit + (n_valid_place/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i) && !is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
						fit = fit - (1/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit + (1/(double)num_de_uns);
					}
					else if(!is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit - PENALTY;
					}
					else{
						cout << "\nOpcao invalida 4!\n"; pera();
					}
				}
				else{
					//esquerda
					if(is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
						fit = fit + (n_valid_place/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i) && !is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
						fit = fit - (1/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit + (1/(double)num_de_uns);
					}
					else if(!is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit - PENALTY;
					}
					//direita
					if(is_connected(ind,k,map,labirinto,dim_map,i,i+1)){
						fit = fit + (n_valid_place/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i) && !is_connected(ind,k,map,labirinto,dim_map,i,i-1)){
						fit = fit - (1/(double)num_de_uns);
					}
					else if(is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit + (1/(double)num_de_uns);
					}
					else if(!is_valid_option(labirinto,dim_map,ind,k,i)){
						fit = fit - PENALTY;
					}
					else{
						cout << "\nOpcao invalida 5!\n"; pera();
					}

				}

			}
		}
	}




	return fit;
}
*/





//-----------------------------------------------------------------------------------------------------------------------
string *load_map(FILE *fl, int *num_linhas_mapa){
    string *mapa;
    *num_linhas_mapa = count_lines(fl) - 1;
    int i_linha = 0;
    mapa = new string[*num_linhas_mapa];
    char line_temp[TAM_MAX_LINHA];
    rewind(fl);
    while(fgets(line_temp,TAM_MAX_LINHA,fl) != NULL){
        int z = 0;
        while(line_temp[z] != '\r' && line_temp[z] != '\n'){line_temp[z] = tolower(line_temp[z]); z++;}
        line_temp[z] = '\0';
        mapa[i_linha] = line_temp;
        i_linha++;
    }
    return mapa;
}
//------------------------------------------------------------------------------
//conta a quantidade de linhas do arquivo
int count_lines(FILE *fl){
    int linhas = 1;
    char c;
    rewind(fl);

    do{
         c = fgetc(fl);
         if(c == '\n')
           linhas++;

    }while(c != EOF);
    rewind(fl);
    return linhas;
}
//------------------------------------------------------------------------------
int **get_reduced_map(int **mapa,Point dim_map,Point *dim_reduced_map){
	int new_dimy = (dim_map.y+1)/2, **new_map;

	new_map = new int*[dim_map.x];
	for(int i=0;i < dim_map.x;i++)
		new_map[i] = new int[new_dimy];

	bool sequence3_0 = false;
	int cont;
	for(int i=0;i<dim_map.x;i++){
		cont = 0;
		sequence3_0 = false;
		for(int j=0;j<dim_map.y;j++){
			if(j<(dim_map.y-2)){
				if(mapa[i][j] == 9){
					new_map[i][cont] = 9;
					sequence3_0=false;
					//cont++;
				}
				else if(mapa[i][j] == 1 && mapa[i][j+1] == 1 && mapa[i][j+2] == 1){
					j = j+2;
					new_map[i][cont] = 1;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 0 && mapa[i][j+2] == 0 && sequence3_0==false){
					j = j+2;
					new_map[i][cont] = 0;
					sequence3_0 = true;
					//cont++;
				}
				else if(mapa[i][j] == 1){
					sequence3_0=false;
					new_map[i][cont] = 1;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 3 && mapa[i][j+2] == 0){
					j = j+2;
					new_map[i][cont] = 3;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 5 && mapa[i][j+2] == 0){
					j = j+2;
					new_map[i][cont] = 5;
				}
				/*else if(mapa[i][j] == 3 && mapa[i][j+1] == 0){
					j = j+2;
					new_map[i][cont] = 3;
					//cont++;
				}
				else if(mapa[i][j] == 5 && mapa[i][j+1] == 0){
					j = j+2;
					new_map[i][cont] = 5;
				}*/
				else if(mapa[i][j] == 0 && sequence3_0 == true){
					sequence3_0 = false;
					new_map[i][cont] = 0;
					//printf("\ninvalido!\n");
				}
				cont++;
			}
			else{
				if(mapa[i][j] == 5)
					new_map[i][cont] = 5;
				else if(mapa[i][j] == 3)
					new_map[i][cont] = 3;
				else{

				}
			}
		}
		new_map[i][new_dimy-1] = 9;
	}

	dim_reduced_map->x = dim_map.x;
	dim_reduced_map->y = new_dimy;

	return new_map;
}
//------------------------------------------------------------------------------
string *build_final_map(int **labirinto,Point dim_labirinto,int **solution_map,Point dim_solution_map){

	string *mapa;
	mapa = new string[dim_labirinto.x];

	char *temp;
	temp = new char[dim_labirinto.y+1];

	int cont;
	bool sequence3_0 = false;

	for(int i=0;i<dim_solution_map.x;i++){
		cont = 0;
		sequence3_0 = false;
		for(int j=0;j<dim_solution_map.y;j++){
				if(solution_map[i][j] == 4){
					labirinto[i][cont] = 4;
					labirinto[i][cont+1] = 4;
					labirinto[i][cont+2] = 4;
					cont = cont + 2;
					sequence3_0 = true;
				}
				else if(solution_map[i][j] == 4 && sequence3_0 == true){
					labirinto[i][cont] = 4;
					sequence3_0 = false;
				}

				cont++;
		}

	}


/*
		for(int i=0;i<dim_labirinto.x;i++){
			for(int j=0;i<dim_labirinto.y;i++){
				if(labirinto[i][j] == 9)
					temp[j] = '+';
				else if(labirinto[i][j] == )
			}
		}*/
		printf("\nbuild final map\n");
		printMapa(labirinto,dim_labirinto); pera();

	return mapa;
}
//------------------------------------------------------------------------------
int **preProcessing(int **mapa,Point dim_map){
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(mapa[i][j] == 9)
				mapa[i][j] = 1;

	return mapa;
}
//------------------------------------------------------------------------------
int **copy_map(int **map,Point dim_map){
	int **copy;
	copy = new int*[dim_map.x];
	for(int i=0;i < dim_map.x;i++)
		copy[i] = new int[dim_map.y];

	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			copy[i][j] = map[i][j];

	return copy;
}
//------------------------------------------------------------------------------
void clone(int **origem,int **destino,Point dim_map){
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			destino[i][j] = origem[i][j];
}
//------------------------------------------------------------------------------
int get_number_of_valid_space(int **map, Point dim_map){
	int valid_space = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 0)
				valid_space++;

	return valid_space;
}
//------------------------------------------------------------------------------
int **str_map2bin_map(string map[], int num_linhas,Point *dim_labirinto){
	int dimx, dimy;
	dimx = num_linhas;
	dimy = map[0].length(); //assume-se q todas as linhas possuem o mesmo tamanho...
	int **bin_map;
	//cout << dimy << endl; string x; cin >> x;

	//criando matriz dinamicamente
	bin_map = new int*[dimx];
	for(int i=0;i < dimx;i++)
		bin_map[i] = new int[dimy];

	char *temp = new char[dimy+1];

	for(int i=0;i < dimx;i++){
		strcpy(temp,map[i].c_str());
		for(int j=0;j < dimy;j++){
			if(temp[j] == ' ')
				bin_map[i][j] = 0;
			else if(temp[j] == 's')
				bin_map[i][j] = 5;
			else if(temp[j] == 'e')
				bin_map[i][j] = 3;
			else if(temp[j] == '+')
				bin_map[i][j] = 9;
			else
				bin_map[i][j] = 1;
		}
	}

	dim_labirinto->x = dimx;
	dim_labirinto->y = dimy;
	delete[] temp;

	return bin_map;
}
//------------------------------------------------------------------------------
Point FindStartPoint(int **map,Point dim_map){
	Point start;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 5){
				start.x = i;
				start.y = j;
				return start;
			}

	return start;
}
//------------------------------------------------------------------------------
Point FindEndPoint(int **map,Point dim_map){
	Point end;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 3){
				end.x = i;
				end.y = j;
				return end;
			}

	return end;
}
//------------------------------------------------------------------------------
//conta a quantidade de lugares validos que foram "marcados"
int count_in_genes(int **solution_map,int **map,Point dim_map){
	int count = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(solution_map[i][j] == 4 && map[i][j] == 0)
				count++;

	return count;
}
//------------------------------------------------------------------------------
//conta a quantidade de lugares invalidos marcados
int count_out_genes(int **solution_map,int **map,Point dim_map){
	int count = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(solution_map[i][j] == 4 && map[i][j] == 1)
				count++;

	return count;
}
//------------------------------------------------------------------------------
//retorna um vetor do tamanho do cromosso, em que cada indice contem 1 ou 0
//1 significa que aquele gene (indice) esta errado e 0 correto
int *get_out_gene(int **solution_map,int **map,Point dim_map){
	int *index_out_gene_cromossomo, tam = dim_map.x*dim_map.y;
	int linha = 0, coluna = 0;
	index_out_gene_cromossomo = new int[tam];

	for(int i=0;i<tam;i++){
		index_out_gene_cromossomo[i] = 0;
		linha = i/dim_map.y;
		if(i == tam)
			coluna = dim_map.y;
		else
			coluna = i % dim_map.y;
		if(solution_map[linha][coluna] == 4 && map[linha][coluna] == 1)
			index_out_gene_cromossomo[i] = 1;
	}


	return index_out_gene_cromossomo;
}
//------------------------------------------------------------------------------
void printMapa(int **map,Point dim_map){
	printf("\n");
	for(int i=0;i<dim_map.x;i++){
		for(int j=0;j<dim_map.y;j++)
			printf("%d",map[i][j]);
		printf("\n");
	}
}
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
double euclidian_distance_2D(Point ponto1,Point ponto2){
	double distance = 0.0;

	distance = pow((ponto1.x - ponto2.x),2) + pow((ponto1.y - ponto2.y),2);

	return sqrt(distance);
}
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
int **InsertSolution(Individual *ind,int k,int **map,Point dim){
	int linha = 0, coluna = 0;

		for(int i=0;i<ind[k].getNumGenes();i++){
			linha = i/dim.y;
			coluna = i % dim.y;
			if(ind[k].getGene(i) == 1)
				map[linha][coluna] = 4;
		}

		return map;
}
//------------------------------------------------------------------------------
CImg<int> update_display(int **map,CImg<int> cimg_labirinto){
	cimg_forXY(cimg_labirinto,x,y){
		if(map[x][y] == 1) //wall
			cimg_labirinto(y,x,0) = cimg_labirinto(y,x,1) = cimg_labirinto(y,x,2) = 0;
		else if(map[x][y] == 0)//free space
			cimg_labirinto(y,x,0) = cimg_labirinto(y,x,1) = cimg_labirinto(y,x,2) = 255;
		else if(map[x][y] == 5){//start
			cimg_labirinto(y,x,0) = 255;
			cimg_labirinto(y,x,1) = 0;
			cimg_labirinto(y,x,2) = 0;
		}
		else if(map[x][y] == 3){//end
			cimg_labirinto(y,x,0) = 0;
			cimg_labirinto(y,x,1) = 255;
			cimg_labirinto(y,x,2) = 0;
		}
		else if(map[x][y] == 4){// caminho...
			cimg_labirinto(y,x,0) = 0;
			cimg_labirinto(y,x,1) = 0;
			cimg_labirinto(y,x,2) = 255;
		}
		else{
		}

	}

	return cimg_labirinto;
}
//---------------------------------------------------------------------------------------------------------------------------
int count_marker_genes(Individual *ind,int k){
	int count = 0;
	for(int i=0;i<ind[k].getNumGenes();i++)
		if(ind[k].getGene(i) == 1)
			count++;

	return count;
}
//-----------------------------------------------------------------------------------------------------------------------
bool is_valid_option(int **labirinto,Point dim_map,Individual *ind,int k,int index){
	int linha = 0, coluna = 0;
	linha = index/dim_map.y;

	int tam = ind[k].getNumGenes();

	if(index == tam){
		coluna = tam;
	}
	else{
		coluna = index % dim_map.y;
	}


	if( (labirinto[linha][coluna] == 0 && ind[k].getGene(index) == 1) || (labirinto[linha][coluna] == 3 && ind[k].getGene(index) == 1) || (labirinto[linha][coluna] == 5 && ind[k].getGene(index) == 1) ){
		//cout << "\nIndividuo: " << k << " :\n"; ind[k].printIndividual(); cout << "\nIndex: " << index << endl;
		//cout << ind[k].getGene(index);
		//cout << "\nPonto: (" << linha << "," << coluna << ") = " << labirinto[linha][coluna] << endl;
		//pera();
		return true;
	}
	//else if(labirinto[linha][coluna] == 1 && ind[k].getGene(index) == 0){
		//return true;
	//}
	else if(labirinto[linha][coluna] == 1 && ind[k].getGene(index) == 1){
			return false;
	}

	return false;

}
//-----------------------------------------------------------------------------------------------------------------------
bool is_connected(Individual *ind,int k,int **map,int **original,Point dim_map,int index1,int index2){
	int linha1 = 0, coluna1 = 0, linha2 = 0, coluna2 = 0;
	linha1 = index1/dim_map.y;
	linha2 = index2/dim_map.y;

	int tam = ind[k].getNumGenes();

	if(index1 == tam){
		coluna1 = tam;
	}
	else{
		coluna1 = index1 % dim_map.y;
	}

	if(index2 == tam){
		coluna2 = tam;
	}
	else{
		coluna2 = index2 % dim_map.y;
	}

	int gene1 = ind[k].getGene(index1), gene2 = ind[k].getGene(index2);

	if( gene1 == gene2 && gene1 == 1 && original[linha1][coluna1] == 0 && original[linha2][coluna2] == 0){
		//cout << "\nIndividuo: " << k << " :\n"; ind[k].printIndividual(); cout << "\nIndex1: " << index1 << "   Index2: " << index2 << endl;
		//cout << ind[k].getGene(index1) << "   " << ind[k].getGene(index2);
		//cout << "\nPonto1: (" << linha1 << "," << coluna1 << ") = " << map[linha1][coluna1] << endl;
		//cout << "Ponto2: (" << linha2 << "," << coluna2 << ") = " << map[linha2][coluna2] << endl;
		//pera();
		return true;
	}

	return false;

}
//-----------------------------------------------------------------------------------------------------------------------
bool is_end_start(Individual *ind,int k,Point dim_map,Point start,Point end){
	//verifica se neste individuo ele possui o gene "start" e "end"
	int index_start = 0, index_end = 0,linha_s = 0, coluna_s = 0, linha_e = 0, coluna_e = 0;
	int num_genes = ind[k].getNumGenes();

	//encontrando indice que guarda a posicao "start"
	for(int i=0;i<num_genes;i++){
		linha_s =  i/dim_map.y;
		coluna_s = i % dim_map.y;
		if(linha_s == start.x && coluna_s == start.y){
			index_start = i;
			i = num_genes;
		}
	}

	//encontrando indice que guarda a posicao "end"
	for(int i=0;i<num_genes;i++){
		linha_e =  i/dim_map.y;
		coluna_e = i % dim_map.y;
		if(linha_e == end.x && coluna_e == end.y){
			index_end = i;
			i = num_genes;
		}
	}


	if(ind[k].getGene(index_start) == 1 && ind[k].getGene(index_end) == 1){
		return true;
		//fit = fit + BONUS;
		//cout << "\nstart: " << "(" << linha_s << "," << coluna_s << ") = " << labirinto[linha_s][coluna_s] << "  gene: " << index_start << " = " << ind[k].getGene(index_start) << "\n";
		//cout << "\nend: " << "(" << linha_e << "," << coluna_e << ") = " << labirinto[linha_e][coluna_e] << "  gene: " << index_end << " = " << ind[k].getGene(index_end) << "\n";
		//pera();
	}
	else{
		return false;
	}

	return false;

}
//-----------------------------------------------------------------------------------------------------------------------
bool is_end_start_connected(Individual *ind,int k,int **map,int **labirinto,Point dim_map,Point start,Point end){
	//verifica se neste individuo ele possui o gene "start" e "end"
	int index_start = 0, index_end = 0,linha_s = 0, coluna_s = 0, linha_e = 0, coluna_e = 0;
	int num_genes = ind[k].getNumGenes();

	//encontrando indice que guarda a posicao "start"
	for(int i=0;i<num_genes;i++){
		linha_s =  i/dim_map.y;
		coluna_s = i % dim_map.y;
		if(linha_s == start.x && coluna_s == start.y){
			index_start = i;
			i = num_genes;
		}
	}

	//encontrando indice que guarda a posicao "end"
	for(int i=0;i<num_genes;i++){
		linha_e =  i/dim_map.y;
		coluna_e = i % dim_map.y;
		if(linha_e == end.x && coluna_e == end.y){
			index_end = i;
			i = num_genes;
		}
	}


	if(ind[k].getGene(index_start) == 1 && ind[k].getGene(index_end) == 1 && is_some_valid_4_connected(index_start,map,labirinto,dim_map) && is_some_valid_4_connected(index_end,map,labirinto,dim_map)){
		return true;
		//fit = fit + BONUS;
		//cout << "\nstart: " << "(" << linha_s << "," << coluna_s << ") = " << labirinto[linha_s][coluna_s] << "  gene: " << index_start << " = " << ind[k].getGene(index_start) << "\n";
		//cout << "\nend: " << "(" << linha_e << "," << coluna_e << ") = " << labirinto[linha_e][coluna_e] << "  gene: " << index_end << " = " << ind[k].getGene(index_end) << "\n";
		//pera();
	}
	else{
		return false;
	}

	return false;

}
//-----------------------------------------------------------------------------------------------------------------------
bool is_some_valid_4_connected(int gene_index,int **map,int **labirinto,Point dim_map){

	Point current_point,norte,sul,leste,oeste;

	current_point.x = gene_index/dim_map.y;
	current_point.y = gene_index % dim_map.y;

	norte = sul = leste = oeste = current_point;

	norte.x--;
	sul.x++;
	leste.y++;
	oeste.y--;
	bool norte_ = false, sul_ = false, leste_ = false, oeste_ = false;
	if(is_in(norte,dim_map)){
		if(map[norte.x][norte.y] == 4 && map[current_point.x][current_point.y] == 4 && labirinto[norte.x][norte.y] == 0 && labirinto[current_point.x][current_point.y] == 0)
			norte_ = true;
	}

	if(is_in(sul,dim_map)){
		if(map[sul.x][sul.y] == 4 && map[current_point.x][current_point.y] == 4 && labirinto[sul.x][sul.y] == 0 && labirinto[current_point.x][current_point.y] == 0)
			sul_ = true;
	}

	if(is_in(leste,dim_map)){
		if(map[leste.x][leste.y] == 4 && map[current_point.x][current_point.y] == 4 && labirinto[leste.x][leste.y] == 0 && labirinto[current_point.x][current_point.y] == 0){
			leste_ = true;
		}
	}

	if(is_in(oeste,dim_map)){
		if(map[oeste.x][oeste.y] == 4 && map[current_point.x][current_point.y] == 4 && labirinto[oeste.x][oeste.y] == 0 && labirinto[current_point.x][current_point.y] == 0){
			oeste_ = true;
		}
	}

	if(norte_ || sul_ || leste_ || oeste_)
		return true;
	else return false;

	return false;
}
//-----------------------------------------------------------------------------------------------------------------------
bool is_gene_end(int gene_index,int **labirinto,Point dim_map){
	int linha = gene_index/dim_map.y, coluna = gene_index % dim_map.y;

	if(is_end(labirinto,linha,coluna))
		return true;
	else return false;

	return false;
}
//-----------------------------------------------------------------------------------------------------------------------
bool is_gene_start(int gene_index,int **labirinto,Point dim_map){
	int linha = gene_index/dim_map.y, coluna = gene_index % dim_map.y;

	if(is_start(labirinto,linha,coluna))
		return true;
	else return false;

	return false;
}
//-----------------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
bool is_wall(int **map,int x, int y){
	if(map[x][y] == 1)
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_start(int **map,int x, int y){
	if(map[x][y] == 5)
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_end(int **map,int x, int y){
	if(map[x][y] == 3)
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_in(Point current_point, Point dim_map){
	if((current_point.x >= 0 && current_point.x < dim_map.x) && (current_point.y >= 0 && current_point.y < dim_map.y))
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_inside(int x,int y,Point dim_map){
	if((x >= 0 && x < dim_map.x) && (y >= 0 && y < dim_map.y))
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool check_north(Point cp,int **map,Point dim){
	if(is_inside(cp.x-1,cp.y,dim))
		if(!is_wall(map,cp.x-1,cp.y))
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool check_south(Point cp,int **map,Point dim){
	if(is_inside(cp.x+1,cp.y,dim))
		if(!is_wall(map,cp.x+1,cp.y))
			return true;

	return false;

}
//-------------------------------------------------------------------------------------------------------------
bool check_east(Point cp,int **map,Point dim){
	if(is_inside(cp.x,cp.y+1,dim))
		if(!is_wall(map,cp.x,cp.y+1))
			return true;

	return false;

}
//-------------------------------------------------------------------------------------------------------------
bool check_west(Point cp,int **map,Point dim){
	if(is_inside(cp.x,cp.y-1,dim))
		if(!is_wall(map,cp.x,cp.y-1))
			return true;

	return false;

}
//-------------------------------------------------------------------------------------------------------------
